In communications technology, there is an ever-increasing demand for high-performance networks, and in particular, a demand for high-performance Internet access. This increased demand has led to the development of improved networks capable of handling larger volumes of data with smaller delays. Nonetheless, as the applications of data transmission mature, the need for quality of service in a network is becoming apparent. “Quality of Service” (QoS) generally refers to guaranteed bounds on the delay, loss rate, available throughput, and/or other measures of reliability. Yet, many of the networks available today do not provide QoS or they provide inadequate QoS for many applications.
Communications networks like the Internet are generally formed with a number of transmission links interconnected with switches. A transmission link is any medium through which signals are communicated and can be single or multiple twisted pairs, optical fiber, coaxial cable, radio links, or other mediums. A switch is a device with one or more input ports and one or more output ports. The switch directs (routes) bits arriving at an input port to the appropriate output port. The bit stream carried by a particular link is often referred to as the “bandwidth” of the link, although this term is technically a misnomer.
The bandwidth of a link is typically shared by multiple data streams and is divided up according to one of several methodologies. For instance, Time Division Multiplexing (TDM) divides bandwidth among multiple data streams by allocating each data stream a time slot. More specifically, using TDM the respective data streams are transmitted for a designated time period in a round robin fashion over a shared transmission link. Referring to the illustration of FIG. 1, to multiplex Z data streams using TDM, the first stream is transmitted for T(1) seconds, then the second stream for T(2) seconds, and so on until the Z-th stream is transmitted for T(Z) seconds. The cycle then repeats starting again with the first stream. Hence, each data stream gets a fraction of the total transmission rate for the shared link, i.e., the stream i (i=1, . . . , Z) gets a fraction
      T    ⁡          (      i      )            [                  T        ⁡                  (          1          )                    +              T        ⁡                  (          2          )                    +      …      +              T        ⁡                  (          Z          )                      ]  of the transmission rate of the link.
In TDM, prior to allocating data to a time slot (sometimes referred to as a “channel”), a periodic framing structure is imposed on the incoming raw bit stream. Bits in the frames are used to monitor bit transmission and to synchronize receivers. One protocol that uses TDM is SONET (synchronous optical network), which further synchronizes the framed data to a common clock. Other TDM protocols, SONET-Light and “digital signal hierarchy” (DS-0, DS-1, etc.), do not synchronize the framed data with a common clock.
Despite the ability to send multiple data streams through a shared link at a guaranteed rate for each data stream, when a particular data stream does not need its time slot on the link, that fraction of the link capacity is wasted because other data streams are not permitted to use that time slot. Thus, when a particular data stream is not utilizing its allocated bandwidth, the link lays idle for the stream's time slot—unavailable for use by any other data stream, leading to an inefficient utilization of available resources.
Similar to TDM is wave division multiplexing (WDM). WDM is often used with optical fibers. Each data stream is assigned a wavelength. Multiple wavelengths can be combined for transmission in a single fiber.
An alternative to TDM and WDM is packetizing. The incoming raw data stream is divided into packets and then the packets are scheduled for transmission on a link according to a scheduling method such as statistical multiplexing. Division into packets also requires imposing a framing structure on the raw bit stream. Unlike the framing structure in TDM, however, the framing structure is not periodic. Successive packets can carry a fixed or variable number of bits, and each packet contains an identifier to enable a receiver to determine how the packet is to be handled. Some packets also include an error-detection field to enable a receiver to determine if the transmission was error-free. Examples of protocols that use these types of packets are IP (Internet Protocol), Frame Relay, Ethernet, PPP (Point-to-Point Protocol), and ATM (asynchronous transfer mode).
Once divided into packets, the packets need to be scheduled for transmission on a link, often using a statistical multiplexing (SM) method. In contrast with TDM, SM does not allocate fixed periodic fractions of the transmission rate of the link to the different data streams. Instead, an SM method schedules packets for transmission depending on the actual needs of the different data streams. In its simplest form, illustrated in FIG. 2, statistical multiplexing schedules packets on the transmission line in the order of their arrival at the switch, i.e., on a first come, first served basis. Although such a scheduling method does not waste communication resources, it cannot guarantee a minimum transmission rate for any particular data stream. There is no predetermined delay for a packet to get to its destination. Other SM methods are known in the art and can provide some minimum transmission rate, but usually there is still the possibility that delivery of a message will be delayed. Therefore, most data communication service providers, although they utilize statistical multiplexing for packet transmission, will not guarantee any minimum quality of service.
Data multiplexed into the links, using TDM, WDM, SM, or other method, is transmitted from source to destination using one of three strategies: circuit switching, datagram (or packet) switching, and virtual circuits.
Circuit switching entails establishing an end-to-end connection to handle the transmission rate of a given data stream before any data is communicated. Hence, in a circuit-switched network, a bit stream flows along a fixed, pre-established sequence of links at a constant rate. Circuit switching is frequently used in combination with TDM in SONET networks and in Digital Signal Hierarchy networks that make up telephone networks. When a user places a telephone call, a signaling protocol enables switches to exchange call control information in order to establish and configure a suitable path.
A datagram network, such as an IP network, utilizes packets as described above. Each packet includes an identification of its destination address. Switches, referred to as “routers” in this technology, maintain tables that indicate the next link for each possible destination address. To maintain these routing tables, the routers regularly exchange information. Nonetheless, each packet is routed individually, and each packet from a particular data stream will not necessarily follow the same path to its destination as other packets from the same stream.
A virtual circuit network, such as ATM, also routes packets, which are called “cells”, as in a datagram network, but it pre-determines a path for the cells to take. Each cell is labeled with a virtual circuit identifier, and every switch maintains a table that specifies the next link for every possible virtual circuit identifier. While virtual circuits can be permanently established, frequently they are “switched.” When they are switched, a suitable path must be determined whenever a new connection is requested. Once a virtual circuit is established, all of the cells for that virtual circuit follow the same route along the virtual channel, thereby guaranteeing the order of cell arrival. Further, because data is sent in cells, these cells can be statistically multiplexed, and can use all available resources efficiently while guaranteeing a minimum quality of service.
Some networks essentially combine different switching strategies. For instance, MPLS (multiprotocol label switching) is a virtual circuit-like mechanism for IP networks. In MPLS, a virtual circuit-like identifier is added to IP packets. The routers then use that MPLS identifier to determine the next link for the packet as well as a scheduling rule. Thus, in IP networks, some routers base their routing decisions on the packet's destination address while others use an MPLS identifier.
Despite the availability of numerous protocols mentioned above, most networking experts agree that by 2005 at least 95% of the telecommunication traffic will consist of IP packets that are generated by voice, multimedia, and traditional data applications. Much of this growth is due to the recent explosion in Internet usage and applications. Yet, these IP packets will not just be transported over datagram networks designed to manage them—these IP packets will also be transported over virtual circuit networks, such as ATM, as well as circuit-switched networks utilizing TDM protocols, e.g., SONET. While these networks can reliably transport IP packets, they cannot guarantee any QoS to the IP packets themselves. For instance, while ATM can guarantee QoS to the cells it transports, it cannot provide QoS to the IP packets that arrive at its switches and that are subdivided into cells. Often, only fragments of packets will be transported in an ATM network, while the remainder of the packet is discarded. These ATM networks, as well as TDM networks, are simply not equipped to provide QoS to IP packets. Yet demand for QoS for IP transported over all networks (regardless of protocol) is expected to grow substantially.